package com.wtx.chapter13;

/**
 * @description: 2-3树
 * @author: wtx
 * @createDate: 2020/6/1
 */
public class Tree23<E extends Comparable<E>> {

    private Node root;
    private Integer size;       //元素的个数

    public Integer getSize(){
        return this.size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    //添加元素
    public void add(E e){
        root = add(root,e);
    }

    private Node add(Node node, E e) {

        if (node==null){
            this.size++;
            return new Node(e);
        }

        if (node.e2 == null && node.left == null){ // 对于2-3树,node.left == null则node.right == null
            if (e.compareTo(node.e1)>0){    // e>e1
                node.e2 = e;
                this.size++;
            }else if (e.compareTo(node.e1)<0){  //e<e1
                node.e2 = node.e1;
                node.e1 = e;
                this.size++;
            }// e==e1不处理
            return node;
        }

        if (node.e1!=null && node.e2!=null && node.left==null){
            if (e.compareTo(node.e1)<0) { //e<e1
                node.left = new Node(e);
                node.right = new Node(node.e2);
                node.e2 = null;
                this.size++;
                return node;
            }else if (e.compareTo(node.e2)>0){  //e>e2
                node.left = new Node(node.e1);
                node.e1 = node.e2;
                node.e2 = null;
                node.right = new Node(e);
                this.size++;
                return node;
            }else if (e.compareTo(node.e1)>0 && e.compareTo(node.e2)<0){ //e1<e<e2
                node.left = new Node(node.e1);
                node.right = new Node(node.e2);
                node.e1 = e;
                node.e2 = null;
                this.size++;
                return node;
            }
        }

        if (e.compareTo(node.e1)<0) //e<e1
            node.left = add(node.left,e);
        else if (node.e2 == null && e.compareTo(node.e1)>0)   //e>e1
            node.right = add(node.right,e);
        else if (node.e2!=null){
            if (e.compareTo(node.e2)>0) //e>e2
                node.right = add(node.right,e);
            else if (e.compareTo(node.e1)>0 && e.compareTo(node.e2)<0) //e1<e<e2
                node.mid = add(node.mid,e);
        }
        return node;
    }


    public Tree23() {
        this.root = null;
        this.size = 0;
    }

    private class Node{
        public E e1,e2;     //结点可以存放一个或两个元素,只有一个元素时放在e1
        public Node left,mid,right;

        public Node(E e1, E e2) { //e1<e2
            this.e1 = e1;
            this.e2 = e2;
            this.left = null;
            this.mid = null;
            this.right = null;
        }

        public Node(E e1) {
            this.e1 = e1;
            this.e2 = null;
            this.left = null;
            this.mid = null;
            this.right = null;
        }
    }
}
